package com.tgy.查找;

import java.util.Arrays;

/***
 * @ClassName: InsertValueSearch
 * @Description: 插值查找
 * @Auther: tanggy3
 * @Date: 20:23 2022/9/20
 * @version : V1.0
 */
public class InsertValueSearch {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70, -1, 900, 4561, 1, 0};
        //int arr[] = { 1, 8, 10, 89,1000,1000, 1234 };
        System.out.println(Arrays.toString(sort(arr, 0, arr.length - 1)));
        System.out.println(insertValueSearch(arr, 0, arr.length - 1, -1));

    }


    /**
     * 插值查找
     *
     * @param arr
     * @param left
     * @param right
     * @param findVal
     * @return
     */
    public static int insertValueSearch(int[] arr, int left, int right, int findVal) {
        if (arr[0] > findVal || arr[arr.length-1] < findVal) return -1;
        if (left > right) {
            return -1;
        }
        int mid = left + (findVal - arr[left])* (right - left) / (arr[right] - arr[left]) ;

        int temp = arr[mid];

        if (findVal > temp) {
            //中间值小，向右递归
            return insertValueSearch(arr, mid+1, right, findVal);
        } else if (findVal < temp) {
            //中间值大向左递归
            return insertValueSearch(arr, left, mid-1, findVal);
        } else {
            //相等，返回
            return mid;
        }

    }

    /**
     * 快速排序
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    static int[] sort(int[] arr, int left, int right) {
        if (left < right) {
            int l = left, r = right, x = arr[left];
            while (l < r) {
                while (l < r && arr[r] >= x) r--;//从右向左寻找小于x的数
                if (l < r) arr[l++] = arr[r];

                while (l < r && arr[l] < x) l++;//从右向左寻找小于x的数
                if (l < r) arr[r--] = arr[l];
            }
            arr[l] = x;
            sort(arr, ++l, right);
            sort(arr, left, --r);
        }
        return arr;
    }

}
